package 链表;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/reorder-list/
 */
public class _143_重排链表 {
    /**
     * 线性表方法
     * 原理是利用将每个链表存入线性表中，通过下标值 来进行获取替换
     * @param head
     */
    public void reorderList(ListNode head) {
        if (head == null && head.next == null) {
            return;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            // 先进行比较  再进行另外的移动  因为可能会将node.next指向自身  这样就是不可避免的死循环
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i).next;
            j--;
        }
        // 将最后一个节点置为null 防止变为循环链表
        list.get(i).next = null;
    }

    /**
     * 寻找链表中点  + 反转链表  + 合并两条链表
     * @param head
     */
    public void reorderListComplex(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode mid = middleNode(head);
        ListNode l2 = mid.next;
        mid.next = null;
        l2 = reverseList(l2);
        mergeTwoList(head, l2);
    }

    /**
     * 寻找链表中点
     * 通过快慢指针来查询  因为 快指针是慢指针的两倍  正好可以计算中点
     * @param head 目标链表
     * @return ListNode
     */
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast.next != null || fast.next.next != null) {
            slow = slow.next;
            fast= fast.next.next;
        }
        return slow;
    }

    /**
     * 反转链表（链表逆序）  通过两个节点通过不停的转化 进行反转
     * @param head 目标链表
     * @return ListNode
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    /**
     * 合并两个链表  通过逆序的插入前边的  类似于双指针
     * @param node1 链表1
     * @param node2 链表2
     */
    public void mergeTwoList(ListNode node1, ListNode node2) {
        ListNode node1_temp;
        ListNode node2_temp;
        while (node1 != null && node2 != null) {
            node1_temp = node1.next;
            node2_temp = node2.next;

            node1.next = node2;
            node1 = node1_temp;

            node2.next = node1;
            node2 = node2_temp;
        }
    }
}
